package dataStructure.graph;

import java.util.LinkedList;

/**
 * 单源最短路径
 */
public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 初始化距离矩阵
     *
     * @param graph 图
     * @return 距离矩阵
     */
    private static int[][] initDistance(GraphMatrix graph) {
        int vertexNum = graph.getVertexNum();
        int[][] result = new int[vertexNum][vertexNum];
        // 初始化距离矩阵
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                result[i][j] = graph.edges[i][j];
                if (i != j && result[i][j] == 0) {
                    result[i][j] = INF;
                }
            }
        }
        return result;
    }

    private static void showInfo(int[] dist, int[] prev) {
        System.out.print("距离向量 dist:");
        for (int val : dist) {
            if (val == INF) {
                System.out.printf("%4s ", "INF");
            } else {
                System.out.printf("%4d ", val);
            }
        }
        System.out.print("\n前驱结点 prev:");
        for (int val : prev) {
            System.out.printf("%4d ", val);
        }
        System.out.println();
    }

    private static void dijkstra(GraphMatrix<String> graph, String value) {
        dijkstra(graph, graph.getVertexIndex(value));
    }

    //计算一个顶点到其它一个顶点的最短距离
    public static void dijkstra(GraphMatrix graph, int v0) {
        int vertexNum = graph.getVertexNum();
        boolean[] visited = new boolean[vertexNum];
        int[][] distance = initDistance(graph);
        int[] dist = new int[vertexNum];
        int[] prev = new int[vertexNum];
        //初始化visited、dist和path
        for (int i = 0; i < vertexNum; i++) {
            //一开始假定取直达路径最短
            dist[i] = distance[v0][i];
            visited[i] = false;
            //直达情况下的最后经由点就是出发点
            if (i != v0 && dist[i] < INF)
                prev[i] = v0;
            else
                prev[i] = -1; //无直达路径
        }
        //初始时源点v0∈visited集，表示v0 到v0的最短路径已经找到
        visited[v0] = true;
        // 下来假设经由一个点中转到达其余各点,会近些,验证之
        // 再假设经由两个点中转,会更近些,验证之,.....
        // 直到穷举完所有可能的中转点
        int minDist;
        int v = 0;
        //除了v0,剩下vertexNum - 1个结点
        for (int i = 0; i < vertexNum - 1; i++) {
            showInfo(dist, prev);
            //挑一个距离最近经由点,下标装入 v
            minDist = INF;
            for (int j = 0; j < vertexNum; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    v = j;// 经由顶点j中转则距离更短
                    minDist = dist[j];
                }
            }
            visited[v] = true;
            /*顶点v并入S，由v0到达v顶点的最短路径为min.
              假定由v0到v，再由v直达其余各点，更新当前最后一个经由点及距离*/
            for (int j = 0; j < vertexNum; j++) {
                if (!visited[j] && distance[v][j] < INF) {
                    if (minDist + distance[v][j] < dist[j]) {
                        //如果多经由一个v点到达j点的 最短路径反而要短,就更新
                        dist[j] = minDist + distance[v][j];
                        //经由点的序号
                        prev[j] = v;
                    }
                }
            }
        }
        printPath(graph, v0, dist, prev);
    }

    //v0为出发节点
    private static void printPath(GraphMatrix graph, int v0, int[] dist, int[] prev) {
        //由于记录的中途节点是倒序的，所以使用栈（先进后出），获得正序
        LinkedList<Integer> stack = new LinkedList<>();
        //打印从出发节点到各节点的最短距离和经过的路径
        for (int i = 0; i < graph.getVertexNum(); i++) {
            int j = i;
            //如果j有中途节点
            while (prev[j] != -1) {
                stack.push(j);          //将j压入堆
                j = prev[j];          //将j的前个中途节点赋给j
            }
            stack.push(j);

            System.out.print(graph.vertexList.get(v0) + "-->" +
                    graph.vertexList.get(i) + " 的最短路径是：" + dist[i]);
            System.out.print(", ");
            //先进后出,获得正序
            while (!stack.isEmpty()) {
                System.out.print(graph.vertexList.get(stack.pop()));//打印堆的头节点
                if (!stack.isEmpty()) {
                    System.out.print("->");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        GraphMatrix<String> graph = new GraphMatrix<>("ABCD");
        graph.type = GraphMatrix.GraphType.DIRECTED_GRAPH;
        graph.addEdge("A", "B", 1);
        graph.addEdge("A", "C", 2);
        graph.addEdge("A", "D", 3);
        graph.addEdge("B", "A", 4);
        graph.addEdge("C", "B", 5);
        graph.addEdge("C", "D", 1);
        graph.addEdge("D", "B", 1);
        graph.addEdge("D", "C", 2);
        graph.information();
        dijkstra(graph, "B");
    }
}
